# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
	# @param two ListNodes
	# @return a ListNode
	def mergeTwoLists(self, l1, l2):
		if l1 is None:
			return l2
		if l2 is None:
			return l1

		main = None
		if l1.val > l2.val:
			main = l2
			l2 = l2.next
		else:
			main = l1
			l1 = l1.next
		end = main
		while (l1 is not None) and (l2 is not None):
			if l1.val <= l2.val:
				end.next = l1
				l1 = l1.next
			else:
				end.next = l2
				l2 = l2.next
			end = end.next
		if l1 is not None:
			end.next = l1
		if l2 is not None:
			end.next = l2
		return main

if __name__ == '__main__':
	n1 = ListNode(1)
	n2 = ListNode(2)
	n3 = ListNode(3)
	n4 = ListNode(4)
	n5 = ListNode(5)
	n6 = ListNode(6)
	n7 = ListNode(7)
	n8 = ListNode(8)
	'''
	n1.next = n3
	n3.next = n5
	n5.next = n7
	n7.next = n8
	n2.next = n4
	n4.next = n6
	'''
	so = Solution()
	a = so.mergeTwoLists(n1, n2)
	while a is not None:
		print(a.val)
		a = a.next
